
import timeit
def Erato(start=2,end=3): #最简单易懂的埃拉托塞尼筛选法
    end=end+1
    isPrime=[True]*end
    isPrime[0]=isPrime[1]=False
    for i in range(2,int(end**0.5)+1): ## 最大值为根号n即可
        if isPrime[i]: # 即对之前已经排除掉的不是质数的数，不用再对它的倍数进行二次排除。
            for j in range(i*i,end,i):  ## i*i start stop step
                isPrime[j]=False

    ans=[i for i in range(start,end) if isPrime[i]]
    return ans

def Erato2(end=3):
    
    if end<3:
        if end==2:
            return [2]
        return None
    
    isPrime=[True]*end

    for i in range(3,int(end**0.5)+1,2):  #此法直接跳过偶数
        if isPrime[i]:
            for j in range(i*i,end,i*2): #i必为奇数，故i的奇数倍必定为偶数，不必考虑
                isPrime[j]=False
   
    return [2]+[i for i in range(3,end,2) if isPrime[i]]

def Erato3(end=3): #最佳做法
    
    if end<3:
        if end==2:
            return [2]
        return None
    
    isPrime=[True]*end

    for i in range(3,int(end**0.5)+1,2): ## 指定步长参数，进行列表切片赋值
        if isPrime[i]: #去除此判断会导致重复更改，当i==9时，仍进行修改。 不影响答案，但影响时间。
            isPrime[i * i::2 * i] = [False] * ((end - i * i - 1) // (2 * i) + 1) 
        # isPrime[i * i::2 * i] = [False]*len(isPrime[i * i::2 * i]) #效果等价于上一句

    return [2]+[i for i in range(3,end,2) if isPrime[i]]


def Euler(num):

    # 全部初始化为0
    prime = [True]*(num+1)
    # 存放素数
    common = []
    for i in range(2, num+1):
        if prime[i]:
            common.append(i)
        for j in common:
            if i*j > num:
                break
            prime[i*j] = False
            #将重复筛选剔除
            if i % j == 0:
                break
            
    return common

def rwh_primes2(n): #高端操作，量力而行
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n//3)
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)//3)      ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
        sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

if __name__=="__main__":
    t=timeit.timeit(stmt="Erato(0,100000)",setup="from prime_table import Erato",number=100) 
    t2=timeit.timeit(stmt="Erato2(100000)",setup="from prime_table import Erato2",number=100) 
    t3=timeit.timeit(stmt="Erato3(100000)",setup="from prime_table import Erato3",number=100) 
    t4=timeit.timeit(stmt="rwh_primes2(100000)",setup="from prime_table import rwh_primes2",number=100) 
    t5=timeit.timeit(stmt="Euler(100000)",setup="from prime_table import Euler",number=100) 
    print(t,t2,t3,t4,t5,sep="\n")
    ans=Erato3(100)
    print(*ans)

# 1.9487581610010238
# 0.7274461990018608
# 0.3663154979876708
# 0.31486770800256636
# 2.6644382960075745

